package com.le.high.class2;

import org.junit.Test;

import java.util.*;

/**
 * 给定一个 N×3 的矩阵 matrix，对于每一个长度为 3 的小数组 arr，都表示一个大楼的三个数 据。
 * arr[0]表示大楼的左边界，arr[1]表示大楼的右边界，arr[2]表示大楼的高度(一定大于 0)。
 * 每座大楼的地基都在 X 轴上，大楼之间可能会有重叠，请返回整体的轮廓线数组。
 * matrix = {    {2,5,6},    {1,7,4},    {4,6,7},    {3,6,5},    {10,13,2},
 * {9,11,3},    {12,14,4},    {10,12,5}    }
 * <p>
 * {{1,2,4},    {2,4,6},    {4,6,7},    {6,7,4},    {9,10,3},    {10,12,5},    {12,14,4}}
 * <p>
 * <p>
 * 思路：
 * 最大高度变化才产生轮廓线
 */
public class Problem01_BuildingOutline {

    // 描述高度变化的对象
    public static class Node {
        public int x; // x轴上的值
        public boolean isAdd;// true为加入，false为删除
        public int h; // 高度

        public Node(int x, boolean isAdd, int h) {
            this.x = x;
            this.isAdd = isAdd;
            this.h = h;
        }
    }

    public static List<List<Integer>> buildingOutline(int[][] matrix) {
        if (matrix == null || matrix[0].length == 0) {
            return null;
        }
        Node[] nodes = new Node[matrix.length * 2];
        // 每一个大楼轮廓数组，产生两个描述高度变化的对象
        for (int i = 0; i < matrix.length; i++) {
            // 上升
            nodes[i * 2] = new Node(matrix[i][0], true, matrix[i][2]);
            // 下降
            nodes[i * 2 + 1] = new Node(matrix[i][1], false, matrix[i][2]);
        }
        // 把描述高度变化的对象数组，按照规定的排序策略排序
        // 排序的比较策略
        // 1，第一个维度的x值从小到大。
        // 2，如果第一个维度的值相等，看第二个维度的值，“加入”排在前，“删除”排在后
        // 3，如果两个对象第一维度和第二个维度的值都相等，则认为两个对象相等，谁在前都行。
        Arrays.sort(nodes, (o1, o2) -> {
            return o1.x != o2.x ? o1.x - o2.x : (o1.isAdd ? 1 : -1);
        });

        // TreeMap就是java中的红黑树结构，直接当作有序表来使用
        TreeMap<Integer, Integer> mapHeightTimes = new TreeMap<>(); // key 高度，value 出现次数
        TreeMap<Integer, Integer> mapXvalueHeight = new TreeMap<>(); // key: 位置， value：最大高度
        for (int i = 0; i < nodes.length; i++) {
            if (nodes[i].isAdd) { // 是添加
                // 没有出现的高度直接新加记录
                if (!mapHeightTimes.containsKey(nodes[i].h)) {
                    mapHeightTimes.put(nodes[i].h, 1);
                } else { // 出现过次数加一
                    mapHeightTimes.put(nodes[i].h, mapHeightTimes.get(nodes[i].h) + 1);
                }
            } else { // 删除
                // 若果次数是1，直接删除
                if (mapHeightTimes.get(nodes[i].h) == 1) {
                    mapHeightTimes.remove(nodes[i].h);
                } else { // 大于1 则次数减一
                    mapHeightTimes.put(nodes[i].h, mapHeightTimes.get(nodes[i].h) - 1);
                }
            }
            // 根据mapHeightTimes中的最大高度，设置mapXvalueHeight表
            if (mapHeightTimes.isEmpty()) { // 如果mapHeightTimes为空，说明最大高度为0
                mapXvalueHeight.put(nodes[i].x, 0);
            } else { // 如果mapHeightTimes不为空，通过mapHeightTimes.lastKey()取得最大高度
                mapXvalueHeight.put(nodes[i].x, mapHeightTimes.lastKey());
            }
        }
        // res为结果数组，每一个List<Integer>代表一个轮廓线，有开始位置，结束位置，高度，一共三个信息
        List<List<Integer>> res = new ArrayList<>();
        // 一个新轮廓线的开始位置
        int start = 0;
        // 之前的最大高度
        int preHeight = 0;
        // 根据mapXvalueHeight生成res数组
        for (Map.Entry<Integer, Integer> entry : mapXvalueHeight.entrySet()) {
            int curX = entry.getKey(); // 当前位置
            int curHeight = entry.getValue(); // 当前最大高度
            // 之前最大高度和当前最大高度不一样时
            if (preHeight != curHeight) {
                if (preHeight != 0) {
                    // 产生轮廓线
                    res.add(Arrays.asList(start, curX, preHeight));
                }
                start = curX;
                preHeight = curHeight;
            }
        }
        return res;
    }

    @Test
    public void test() {
        int[][] matrix = {
                {2, 5, 6},
                {1, 7, 4},
                {4, 6, 7},
                {3, 6, 5},
                {10, 13, 2},
                {9, 11, 3},
                {12, 14, 4},
                {10, 12, 5}
        };
        List<List<Integer>> lists = buildingOutline(matrix);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }
}
